package 中等.数学;

/**
 * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，
 * 它们的乘积也表示为字符串形式。
 * 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/multiply-strings
 */
public class 字符串相乘_43 {

    public static void main(String[] args) {

        System.out.println(multiply("67671277416626746657687631784163120468201083678333022807", "6767127741662674665768763178416312046820108367833302280767671277416626746657687631784163120468201083678333022807"));

    }

    /**
     * 模拟
     * num2 的每一位分别和 num1 相乘，然后相加，注意补 0
     *
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply(String num1, String num2) {
        String ans = "0";
        int rightZero = 0;
        int num2Idx = num2.length() - 1;

        while (rightZero < num2.length()) {
            int[] curAns = new int[Math.max(num1.length(), num2.length()) * 2];
            int curIdx = rightZero;

            int pre = 0;
            int mul1 = num2.charAt(num2Idx) - '0';

            for (int i = num1.length() - 1; i >= 0; i--) {
                int a = mul1 * (num1.charAt(i) - '0') + pre;
                curAns[curIdx] = a % 10;
                pre = a / 10;

                curIdx++;
            }
            if (pre > 0) {
                curAns[curIdx] = pre;
            }

            ans = add(ans, curAns);

            num2Idx--;
            rightZero++;
        }
        return ans.length() == 0 ? "0" : new StringBuilder(ans).reverse().toString();
    }

    private static String add(String num1Str, int[] curAns) {
        int[] ans = new int[Math.max(num1Str.length(), curAns.length) + 1];
        int pre = 0;
        int idx = 0;

        while (idx < ans.length) {
            int sum = 0;
            if (idx < num1Str.length()) {
                sum += num1Str.charAt(idx) - '0';
            }
            if (idx < curAns.length) {
                sum += curAns[idx];
            }

            ans[idx] = (sum + pre) % 10;
            pre = (sum + pre) / 10;
            idx++;
        }
        if (pre > 0) {
            ans[idx] = pre;
        }

        StringBuilder stringBuilder = new StringBuilder();
        idx = ans.length - 1;

        while (idx >= 0 && ans[idx] == 0) idx--;
        while (idx >= 0) {
            stringBuilder.append(ans[idx]);
            idx--;
        }
        return stringBuilder.reverse().toString();
    }

}
